package raytracer.objects;

import raytracer.main.*;
import raytracer.misc.*;
import raytracer.math.*;

import java.util.*;

public class UniformGrid extends SpaceStructure {

	private BoundingBox sceneBB;
	private List<ThreeDObject> objects,finiteObjects,infiniteObjects;
	private List[][][] gridContent;
	private final int GRIDRES=AppWideConstants.GRIDRES;
	private final Vector3d CELLSIZE;	
	
	@SuppressWarnings("unchecked")
	public UniformGrid(Scene s) {
		sceneBB=new BoundingBox(s);
		CELLSIZE=new Vector3d(		// Gives us x, y and z cellsize
				(sceneBB.getMaxValues().x-sceneBB.getMinValues().x)/GRIDRES,
				(sceneBB.getMaxValues().y-sceneBB.getMinValues().y)/GRIDRES,
				(sceneBB.getMaxValues().z-sceneBB.getMinValues().z)/GRIDRES
		);
		objects=s.getObjectList();
		finiteObjects=new ArrayList<ThreeDObject>();
		infiniteObjects=new ArrayList<ThreeDObject>();
		for (ThreeDObject obj:objects) {
			if (obj.isInfinite())
				infiniteObjects.add(obj);
			else
				finiteObjects.add(obj);
		}
		
		gridContent=new List[GRIDRES][GRIDRES][GRIDRES];
		
		/* We need to sort the finite objects into the grid */
		for (ThreeDObject obj:finiteObjects) {
			Vector3d objMinValues=obj.getMinValues();
			Vector3d objMaxValues=obj.getMaxValues();
			/* Translate the object coordinates to boundig box's origin */
			objMinValues.sub(sceneBB.getMinValues());
			objMaxValues.sub(sceneBB.getMinValues());
			
			/* Determine start and end values for sorting iteration */
			Vector3d minGrid=new Vector3d(
					(int)(objMinValues.x/CELLSIZE.x),
					(int)(objMinValues.y/CELLSIZE.y),
					(int)(objMinValues.z/CELLSIZE.z)
			);
			
			Vector3d maxGrid=new Vector3d(
					(int)(objMaxValues.x/CELLSIZE.x),
					(int)(objMaxValues.y/CELLSIZE.y),
					(int)(objMaxValues.z/CELLSIZE.z)
			);
						
			/* Values may be GRIDRES so they must be set to GRIDRES-1 then */
			minGrid.set(
					minGrid.x==GRIDRES?GRIDRES-1:minGrid.x,
					minGrid.y==GRIDRES?GRIDRES-1:minGrid.y,
					minGrid.z==GRIDRES?GRIDRES-1:minGrid.z
			);
			
			maxGrid.set(
					maxGrid.x==GRIDRES?GRIDRES-1:maxGrid.x,
					maxGrid.y==GRIDRES?GRIDRES-1:maxGrid.y,
					maxGrid.z==GRIDRES?GRIDRES-1:maxGrid.z
			);
														
			for (int x=(int)minGrid.x;x<=maxGrid.x;x++) {
				for (int y=(int)minGrid.y;y<=maxGrid.y;y++) {
					for (int z=(int)minGrid.z;z<=maxGrid.z;z++) {
						if (gridContent[x][y][z]==null)
							gridContent[x][y][z]=new ArrayList<ThreeDObject>();
						gridContent[x][y][z].add(obj);
					}
				}
			}
		}
		
	}
	
	@SuppressWarnings("unchecked")
	public ThreeDObject intersect(Ray ray, Vector3d intersectionPoint, Vector3d normal) {
		Vector3d absolutePosition=new Vector3d();
		Vector3d gridPosition=new Vector3d();
		Vector3d origin=new Vector3d(ray.getOrigin());
		Vector3d direction=new Vector3d(ray.getDirection());
		Vector3d tMax=new Vector3d();
		Vector3d tDelta=new Vector3d();
		Vector3d step=new Vector3d();
		Vector3d out=new Vector3d();
		List<ThreeDObject> cellContent;
		ThreeDObject nearestObject=null;
		double tNearestObject=Double.POSITIVE_INFINITY;
		Vector3d tempIntersectionPoint=new Vector3d();
		Vector3d tempNormal=new Vector3d();
				
		/* First check all infinite objects */
		for (ThreeDObject infObject:infiniteObjects) {
			
			/* Only pass Vectors for intersectionPoint and normal if we need them */
			Double tInfObject=infObject.intersect(
					ray,
					intersectionPoint!=null?tempIntersectionPoint:null,
					normal!=null?tempNormal:null
			);
			if (tInfObject!=null && tInfObject<tNearestObject && tInfObject-AppWideConstants.EPSILON>0) {
				tNearestObject=tInfObject;
				nearestObject=infObject;
				
				/* Maybe we don't need these values, so don't always compute them */
				if (intersectionPoint!=null)
					intersectionPoint.set(tempIntersectionPoint);
				if (normal!=null)
					normal.set(tempNormal);
			}
		}
				
		/* Do we hit the bounding box? If not we can leave this (@todo check infinite objects!) */
		double[] tBoundingBoxNF=sceneBB.intersect(ray);
		if (tBoundingBoxNF==null) {
			return nearestObject;
		}
		
		double tBoundingBox=tBoundingBoxNF[0];
		
		/* Camera within grid -> Entry point at ray's origin */
		if (tBoundingBox<0) {
			absolutePosition.set(origin.x,origin.y,origin.z);
		}
		/* Camera somewhere in outer space :P ... entry point equals intersection point */
		else {
			absolutePosition.set(
					origin.x+direction.x*tBoundingBox,
					origin.y+direction.y*tBoundingBox,
					origin.z+direction.z*tBoundingBox
			);
		}
		
		/* Determine the grid steps which just depend on the ray's direction */
		step.set(
				Math.signum(direction.x),
				Math.signum(direction.y),
				Math.signum(direction.z)
		);
		
		/* Determine where we *may* leave the grid */
		out.set(
				direction.x<0?-1:GRIDRES,
				direction.y<0?-1:GRIDRES,
				direction.z<0?-1:GRIDRES
		);
		
		/* Find the grid cells we hit with our ray */
		gridPosition.set(
				(int)((absolutePosition.x-sceneBB.getMinX())/CELLSIZE.x),
				(int)((absolutePosition.y-sceneBB.getMinY())/CELLSIZE.y),
				(int)((absolutePosition.z-sceneBB.getMinZ())/CELLSIZE.z)
		);
		
		/* Max values may be GRIDRES so they must be set to GRIDRES-1 then */
		gridPosition.set(
				gridPosition.x==GRIDRES?GRIDRES-1:gridPosition.x,
				gridPosition.y==GRIDRES?GRIDRES-1:gridPosition.y,
				gridPosition.z==GRIDRES?GRIDRES-1:gridPosition.z						
		);
		
		/* Values of t for traveling one cell */
		tDelta.x=Math.abs(CELLSIZE.x/direction.x);
		tDelta.y=Math.abs(CELLSIZE.y/direction.y);
		tDelta.z=Math.abs(CELLSIZE.z/direction.z);
		
		/* When is the first cell boundary hit? */
		tMax.set(
				step.x>0?Math.abs((CELLSIZE.x-((absolutePosition.x-sceneBB.getMinX())%CELLSIZE.x))/direction.x)
						:Math.abs(((absolutePosition.x-sceneBB.getMinX())%CELLSIZE.x)/direction.x),
				step.y>0?Math.abs((CELLSIZE.y-((absolutePosition.y-sceneBB.getMinY())%CELLSIZE.y))/direction.y)
						:Math.abs(((absolutePosition.y-sceneBB.getMinY())%CELLSIZE.y)/direction.y),
				step.z>0?Math.abs((CELLSIZE.z-((absolutePosition.z-sceneBB.getMinZ())%CELLSIZE.z))/direction.z)
						:Math.abs(((absolutePosition.z-sceneBB.getMinZ())%CELLSIZE.z)/direction.z)
		);
				
		/* Finally traverse the grid! */
		while (true) {
			if ((cellContent=gridContent[(int)gridPosition.x][(int)gridPosition.y][(int)gridPosition.z])!=null) {
			
				for (ThreeDObject cellObject:cellContent) {
					if (cellObject.getRayID()==ray.getRayID()) {
						continue;
					}
					else {
						cellObject.setRayID(ray.getRayID());
					}
					
					/* Only pass Vectors for intersectionPoint and normal if we need them */
					Double tCellObject=cellObject.intersect(
							ray,
							intersectionPoint!=null?tempIntersectionPoint:null,
							normal!=null?tempNormal:null
					);
					
					if (tCellObject!=null && tCellObject<tNearestObject && tCellObject-AppWideConstants.EPSILON>0) {
						tNearestObject=tCellObject;
						nearestObject=cellObject;
						
						/* Maybe we don't need these values, so don't always compute them */
						if (intersectionPoint!=null)
							intersectionPoint.set(tempIntersectionPoint);
						if (normal!=null)
							normal.set(tempNormal);
					}
				}
			}
						
			boolean c1=tMax.x<tMax.y;
			boolean c2=tMax.x<tMax.z;
			boolean c3=tMax.y<tMax.z;
			
			if (c1 && c2) {
				gridPosition.x+=step.x;
				if (gridPosition.x==out.x) {
					return nearestObject;
				}
				tMax.x+=tDelta.x;
			}
			else if (((c1 && ! c2) || (!c1 && !c3))) {
				gridPosition.z+=step.z;
				if (gridPosition.z==out.z) {
					return nearestObject;
				}
				tMax.z+=tDelta.z;
			}
			else if (!c1 && c3) {
				gridPosition.y+=step.y;
				if (gridPosition.y==out.y) {
					return nearestObject;
				}
				tMax.y+=tDelta.y;				
			}
		}
		
	}
}